#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2025/4/8
# @USER    : Shengji He
# @File    : CountNegativeNumbersInSortedMatrix.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List

"""
- Array
- Binary Search
- Matrix
"""


class Solution:
    """
    [1351. Count Negative Numbers in a Sorted Matrix](https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/)

    Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

    Example 1:

        Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
        Output: 8
        Explanation: There are 8 negatives number in the matrix.

    Example 2:

        Input: grid = [[3,2],[1,0]]
        Output: 0

    Constraints:
        - m == grid.length
        - n == grid[i].length
        - 1 <= m, n <= 100
        - -100 <= grid[i][j] <= 100
    """

    def countNegatives(self, grid: List[List[int]]) -> int:
        if len(grid) < 1:
            return 0
        n = len(grid[0])
        if n < 1:
            return 0
        negative_nums = 0
        idx = n
        for i in grid:
            idx = self.binary_search(i, idx)
            negative_nums += n - idx
        return negative_nums

    def binary_search(self, grid: List[int], right: int = None) -> int:
        """return the index of first negtive number"""
        left = 0
        if right is None:
            right = len(grid)
        while left < right:
            mid = (left + right) // 2
            if grid[mid] >= 0:
                left = mid + 1
            else:
                right = mid
        return left

    def countNegatives_v2(self, grid: List[List[int]]) -> int:
        i, j, count = 0, len(grid[0]) - 1, 0

        while i < len(grid) and j >= 0:
            if grid[i][j] < 0:
                count += len(grid) - i
                j -= 1
            else:
                i += 1

        return count


if __name__ == '__main__':
    grid = [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]]

    S = Solution()
    print(S.countNegatives(grid))
    print(S.countNegatives_v2(grid))
    print('done')
